/*
 * @lc app=leetcode id=132 lang=cpp
 *
 * [132] Palindrome Partitioning II
 */
class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        vector<vector<bool>> memo(len, vector<bool>(len, false));
        vector<vector<int>> score(len, vector<int>(len, 0));

        for (int i=0; i<len; i++) {
            for (int j=i; j<len; j++) {
                memo[i][j] = isPa(s, i, j);
            }
        }
        int gap = 1;
        while (gap < len) {
            for (int i=0; i < len; i++) {
                int j = i+gap;
                if (j >= len) {
                    break;
                }
                score[i][j] = 0;
                if (!memo[i][j]) {
                    int minVal = INT_MAX, val;
                    for (int k=i; k<j; k++) {
                        val = score[i][k] + score[k+1][j] + 1;
                        minVal = std::min(minVal, val);
                    }
                    score[i][j] = minVal;
                }
            }
            gap++;
        }
        return score[0][len-1];
    }

    bool isPa(string& s, int i, int j) {
        bool valid = true;

        while (i < j) {
            if (s[i] != s[j]) {
                valid = false;
                break;
            }
            i++;
            j--;
        }

        return valid;
    }
};

